package _05_二叉树;

import java.util.ArrayList;
import java.util.Stack;

public class _106_从中序与后序遍历序列构造二叉树 {

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder.length == 0) return null;
        ArrayList<TreeNode> nodes = new ArrayList<>();
        for (int i = postorder.length - 1; i >= 0 ; i--) {
            int cur = postorder[i];
            int index = getIndex(inorder, cur);
            if (index > 0) {
                int nextEle = inorder[index - 1];
                if (isLeft(postorder, i, nextEle)) {
                    TreeNode parent = null;
                    for (TreeNode treeNode : nodes) {
                        TreeNode node = node(treeNode, cur);
                        if (node != null) {
                            parent = node;
                        }
                    }
                    // 左子树
                    TreeNode child = new TreeNode(nextEle);
                    if (parent == null) {
                        parent = new TreeNode(cur, child, null);
                        nodes.add(parent);
                    } else {
                        parent.left = child;
                    }
                } else {
                    TreeNode parent = null;
                    TreeNode curNode = null;
                    // 集合中寻找节点
                    int x = -1;
                    for (int j = 0; j < nodes.size(); j++) {
                        if (node(nodes.get(j), cur) != null) {
                            curNode = nodes.get(j);
                            x = j;
                        }
                        TreeNode node = node(nodes.get(j), nextEle);
                        if (node != null) {
                            parent = node;
                        }
                    }


                    if (curNode == null) {
                        curNode = new TreeNode(cur);
                    } else {
                        nodes.remove(x);
                    }

                    // 左右添加
                    if (parent.right == null) {
                        parent.right = curNode;
                    } else if (parent.left == null) {
                        parent.left = curNode;
                    }
                }
            } else {
                nodes.add(new TreeNode(cur));
            }
        }
        return nodes.get(0);
    }

    public int getIndex(int[] ary, int ele) {
        for (int i = 0; i < ary.length; i++) {
            if (ele == ary[i]) return i;
        }
        return -1;
    }

    public boolean isLeft(int[] ary, int index, int ele) {
        for (int i = 0; i < index; i++) {
            if (ary[i] == ele) return true;
        }
        return false;
    }

    public TreeNode node(TreeNode root, int value) {
        if (root == null) return null;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            root = stack.pop();

            if (root.val == value) return root;

            if (root.right != null) stack.push(root.right);

            if (root.left != null) stack.push(root.left);
        }
        return null;
    }
}
